package com.ls.que121_125;

import com.ls.utils.TreeNode;

/**
 * @author ：ls
 * @date ：2022/4/5 13:27
 * @description：...
 */
public class MaxPathSum {
    int max_path_val = -1001;
    public int maxPathSum(TreeNode root) {
        split(root);
        return max_path_val;
    }

    public void split(TreeNode node) {

        int left = travel(node.left);
        int right = travel(node.right);

        int val = node.val;
        if (left>0)
            val += left;
        if (right>0)
            val += right;

        max_path_val = Math.max(max_path_val, val);

        if (node.left !=null)
            split(node.left);
        if (node.right!=null)
            split(node.right);
    }

    public int travel(TreeNode node){
        if (node == null)
            return 0;

        int left = travel(node.left);
        int right = travel(node.right);

        return Math.max(Math.max(node.val, node.val + left), node.val+right);
    }
}
